# Linked List
์ฐ์์ ์ธ ๋ฉ๋ชจ๋ฆฌ ์์น์ ์ ์ฅ๋์ง ์๋ ์ ํ ๋ฐ์ดํฐ ๊ตฌ์กฐ
(ํฌ์ธํฐ๋ฅผ ์ฌ์ฉํด์ ์ฐ๊ฒฐ๋๋ค)
๊ฐ ๋ ธ๋๋ ๋ฐ์ดํฐ ํ๋์ ๋ค์ ๋ ธ๋์ ๋ํ ์ฐธ์กฐ๋ฅผ ํฌํจํ๋ ๋ ธ๋๋ก ๊ตฌ์ฑ
# ์ Linked List๋ฅผ ์ฌ์ฉํ๋?
๋ฐฐ์ด์ ๋น์ทํ ์ ํ์ ์ ํ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋๋ฐ ์ฌ์ฉํ ์ ์์ง๋ง ์ ํ ์ฌํญ์ด ์์
๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ ๊ณ ์ ๋์ด ์์ด ๋ฏธ๋ฆฌ ์์์ ์์ ๋ํด ํ ๋น์ ๋ฐ์์ผ ํจ
์๋ก์ด ์์๋ฅผ ์ฝ์ ํ๋ ๊ฒ์ ๋น์ฉ์ด ๋ง์ด ๋ฌ (๊ณต๊ฐ์ ๋ง๋ค๊ณ , ๊ธฐ์กด ์์ ์ ๋ถ ์ด๋)
# ์ฅ์
๋์ ํฌ๊ธฐ
์ฝ์ /์ญ์ ์ฉ์ด
# ๋จ์
์์๋ก ์ก์ธ์ค๋ฅผ ํ์ฉํ ์ ์์. ์ฆ, ์ฒซ ๋ฒ์งธ ๋ ธ๋๋ถํฐ ์์ฐจ์ ์ผ๋ก ์์์ ์ก์ธ์ค ํด์ผํจ (์ด์ง ๊ฒ์ ์ํ ๋ถ๊ฐ๋ฅ)
ํฌ์ธํฐ์ ์ฌ๋ถ์ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ๋ชฉ๋ก์ ๊ฐ ์์์ ํ์
๋ ธ๋ ๊ตฌํ์ ์๋์ ๊ฐ์ด ๋ฐ์ดํฐ์ ๋ค์ ๋ ธ๋์ ๋ํ ์ฐธ์กฐ๋ก ๋ํ๋ผ ์ ์๋ค
// A linked list node
struct Node
{
int data;
struct Node *next;
};
# Single Linked List
๋ ธ๋ 3๊ฐ๋ฅผ ์๋ ์ฝ๋๋ฅผ ๋ง๋ค์ด๋ณด์
head second third
| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | 3 | # |
+---+---+ +---+---+ +----+----+
์์ค ์ฝ๋ (opens new window)
# ๋ ธ๋ ์ถ๊ฐ
- ์์ชฝ์ ๋ ธ๋ ์ถ๊ฐ
void push(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
- ํน์ ๋ ธ๋ ๋ค์์ ์ถ๊ฐ
void insertAfter(struct Node* prev_node, int new_data){
if (prev_node == NULL){
printf("์ด์ ๋
ธ๋๊ฐ NULL์ด ์๋์ด์ผ ํฉ๋๋ค.");
return;
}
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
- ๋์ชฝ์ ๋ ธ๋ ์ถ๊ฐ
void append(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node *last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL){
*head_ref = new_node;
return;
}
while(last->next != NULL){
last = last->next;
}
last->next = new_node;
return;
}